← All Articles

[SW Expert Academy] 4112. 피라미드 탐험

Posted on

문제 :

민지가 이상한 피라미드를 발견했다.

이 피라미드는 아래와 같이, 같은 크기의 무수히 많은 원 모양의 방들로 구성되어 있다.

image

피라미드를 조사하던 중 민지는 보물이 있는 방의 위치를 알아내어 그곳으로 이동하려 한다.

민지는 인접한 방으로만 이동할 수 있으며, 두 방이 인접하려면 두 방 사이에 접점이 존재해야 한다.

예를 들어, 5번 방은 2번, 3번, 4번, 6번, 8번, 9번과는 인접하지만 1번, 7번과는 인접하지 않는다.

또한, 1번 방과 인접한 방은 2번과 3번뿐이다.

1 단위시간에 인접한 한 방으로 이동할 수 있다고 가정하자.

민지와 보물이 있는 방의 위치가 주어질 때, 민지가 보물을 찾을 때까지 걸리는 최소시간을 구하는 프로그램을 작성하시오.


입력 :

첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다.

각 테스트 케이스에 해당하는 줄에는 두 개의 자연수 a, b(1 ≤ a, b ≤ 10,000)가 주어진다. 두 자연수는 각각 민지와 보물이 위치해 있는 방의 번호이다.


출력 :

각 테스트 케이스마다 해당하는 줄에 민지가 보물을 찾아가는데 필요한 최소 단위시간을 출력한다.



풀이 :

image

처음에는 피라미드 형태를 어떻게 만들어서 탐색해야할지 감이 오지 않았다. 하지만 피라미드 형태의 그림을 계단식 형태 배열로 저장하니 6가지 탐색방향으로 피라미드 맵과 같은 탐색이 가능했다.

사실 본 문제의 경우 피라미드 형태의 방들을 배열에 적합하게 매칭하여 탐색할 수 있게끔 만드는 것을 생각해 내는 것이 키 포인트인 듯 하다. 그 외의 로직은 일반 bfs 방식과 동일하게 6가지 방향으로 방문 여부를 체크하며 탐색을 진해해주면 최소 탐색시간을 구해낼 수 있다.



코드 :

코드 보기/접기 
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
typedef struct Qnode {
    int x, y, cnt;
}Qnode;
int map[150][150], fin, di[6] = {0, 1, 1, 0, -1, -1}, dj[6] = {1, 1, 0, -1, -1, 0};
bool visit[150][150];

void init() {
    int num = 1;
    for(int i=1; i<150; i++){
        for(int j=1; j<=i; j++) {
            map[i][j] = num++;
            if(num>10000) return;
        }
    }
}

int bfs(int stx, int sty) {
    memset(visit, false, sizeof(visit));
    queue<Qnode> q;
    q.push(Qnode{stx, sty, 0});
    visit[stx][sty] = true;

    while(!q.empty()) {
        int curx = q.front().x, cury = q.front().y, curcnt = q.front().cnt;
        q.pop();
        if(map[curx][cury] == fin) return curcnt;

        for(int k=0; k<6; k++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if(cmpx < 1 || cmpx >=150 || cmpy < 1 || cmpy >= 150) continue;
            if(!map[cmpx][cmpy] || visit[cmpx][cmpy]) continue;
            q.push(Qnode{cmpx, cmpy, curcnt + 1});
            visit[cmpx][cmpy] = true;
        }
    }
}

int testCase() {
    int start, cmpsum = 0, stx, sty;
    cin >> start >> fin;

    for(int i=1; i<150; i++) {
        cmpsum += i;
        if(cmpsum >= start) {
            for(int j=1; j<=i; j++)
                if(map[i][j] == start) {
                    stx = i;
                    sty = j;
                    break;
                }
            break;
        }
    }

    return bfs(stx, sty);
}

int main() {
    init();

    int tc;
    cin >> tc;
    for(int k=1; k<=tc; k++)
        cout << '#' << k << ' ' << testCase() << '\n';
    return 0;
}


AlgorithmalgorithmSW ExpertC++